package code.oldCode.feishuSpecializedTraining.back_trace;

import java.util.*;

/**
 * @author 26029
 * @date 2025/3/18
 * @description
 */
public class MyBackTrace5 {
    // 51. N 皇后
    public List<List<String>> solveNQueens(int n) {
        // 自己做的first版本：常规的回溯办法，递归每一个位置
        List<List<String>> lists = new ArrayList<>();
        int[][] attack = new int[n][n]; // 是否能被攻击到，默认为0，数字代表当前这个位置被几个皇后盯上
        List<int[]> queens = new ArrayList<>();
        backTraceNQueens(0, 0, queens, n, lists, attack);
        return lists;
    }

    private void backTraceNQueens(int x, int y, List<int[]> queens, int n, List<List<String>> lists, int[][] attack) {
        if (queens.size() == n) {
            lists.add(generateMap(n, queens));
            return;
        }
        for (int i = 0; i < n; i++) {
            // 递归只能选择更往后的节点，避免重复结果
            if (i < x)
                continue;
            // 剪枝，剩下的行数不够选了，直接break，没有这一步效率拉跨
            if (queens.size() < i)
                break;
            for (int j = 0; j < n; j++) {
                // 递归只能选择更往后的节点，避免重复结果
                if (i == x && j < y)
                    continue;
                // 如果被攻击，则不能在这个位置
                if (attack[i][j] != 0)
                    continue;
                // 加进去之后，改变一下attack
                queens.add(new int[]{i, j});
                setAttack(i, j, n, attack, true);
                backTraceNQueens(i, j, queens, n, lists, attack);
                // 移出去之后，改变一下attack
                queens.remove(queens.size() - 1);
                setAttack(i, j, n, attack, false);
            }
        }
    }

    private void setAttack(int x, int y, int n, int[][] attack, boolean isAdd) {
        int updateVal = isAdd ? 1 : -1;
        for (int i = 0; i < n; i++) {
            attack[x][i] += updateVal;
            attack[i][y] += updateVal;
            if (x + i < n && y + i < n)
                attack[x + i][y + i] += updateVal;
            if (x + i < n && y - i >= 0)
                attack[x + i][y - i] += updateVal;
            if (x - i >= 0 && y + i < n)
                attack[x - i][y + i] += updateVal;
            if (x - i >= 0 && y - i >= 0)
                attack[x - i][y - i] += updateVal;
        }
    }

    private List<String> generateMap(int n, List<int[]> queens) {
        char[][] chars = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                chars[i][j] = '.';
            }
        }
        for (int[] ints : queens) {
            chars[ints[0]][ints[1]] = 'Q';
        }
        List<String> stringList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            stringList.add(new String(chars[i]));
        }
        return stringList;
    }

    public List<List<String>> solveNQueens_(int n) {
        // 尝试用4个map，代表：一行，一列，正比斜列，反比斜列，主要区别在于一个位置被占与否的表达方式不同
        // 理论上用map避免了使用数组int[][] attack更新时的O(n)的开销
        List<List<String>> lists = new ArrayList<>();
        Map<Integer, Integer> mapColumn = new HashMap<>();
        Map<Integer, Integer> mapRow = new HashMap<>();
        Map<Integer, Integer> mapDirect = new HashMap<>();
        Map<Integer, Integer> mapReverse = new HashMap<>();
        List<int[]> queens = new ArrayList<>();
        backTraceNQueens_(0, 0, queens, n, lists, mapColumn, mapRow, mapDirect, mapReverse);
        return lists;
    }

    private void backTraceNQueens_(int lastX, int lastY, List<int[]> queens, int n,
                                   List<List<String>> lists,
                                   Map<Integer, Integer> mapColumn,
                                   Map<Integer, Integer> mapRow,
                                   Map<Integer, Integer> mapDirect,
                                   Map<Integer, Integer> mapReverse) {
        if (queens.size() == n) {
            lists.add(generateMap(n, queens));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (i < lastX) continue; // 逻辑，不能选比之前行数小的，防止重复
            if (queens.size() < i) break; // 剪枝，剩下的行数不够选了，直接break
            for (int j = 0; j < n; j++) {
                if (i == lastX && j < lastY) continue; // 逻辑，若选择与上一行相同的行，则不能选择比之前列数小的，防止重复
                if (mapColumn.getOrDefault(j, 0) > 0) continue;
                if (mapRow.getOrDefault(i, 0) > 0) continue;
                if (mapDirect.getOrDefault(i - j, 0) > 0) continue;
                if (mapReverse.getOrDefault(i + j, 0) > 0) continue;

                queens.add(new int[]{i, j});

                mapColumn.put(j, mapColumn.getOrDefault(j, 0) + 1);
                mapRow.put(i, mapRow.getOrDefault(i, 0) + 1);
                mapDirect.put(i - j, mapDirect.getOrDefault(i - j, 0) + 1);
                mapReverse.put(i + j, mapReverse.getOrDefault(i + j, 0) + 1);

                backTraceNQueens_(i, j, queens, n, lists, mapColumn, mapRow, mapDirect, mapReverse);

                mapColumn.put(j, mapColumn.get(j) - 1);
                mapRow.put(i, mapRow.get(i) - 1);
                mapDirect.put(i - j, mapDirect.get(i - j) - 1);
                mapReverse.put(i + j, mapReverse.get(i + j) - 1);

                queens.remove(queens.size() - 1);
            }
        }
    }

    // 37. 解数独
    boolean isFind = false;
    public void solveSudoku(char[][] board) {
        // 注意，1：只需要考虑（遍历）空的地方，2：使用boolean[][]而不是Set提升效率
        boolean[][] partSet = new boolean[9][10];
        boolean[][] rowSet = new boolean[9][10];
        boolean[][] columnSet = new boolean[9][10];
        List<int[]> dotPos = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    dotPos.add(new int[]{i, j});
                    continue;
                }
                int num = board[i][j] - '0';
                partSet[getEdge(i, j)][num] = true;
                rowSet[i][num] = true;
                columnSet[j][num] = true;
            }
        }
        solveSudokuBackTrace(0, dotPos, board, partSet, rowSet, columnSet);
    }

    private void solveSudokuBackTrace(int index, List<int[]> dotPos, char[][] board, boolean[][] partSet, boolean[][] rowSet, boolean[][] columnSet) {
        if (index == dotPos.size()) {
            isFind = true;
            return;
        }
        int i = dotPos.get(index)[0];
        int j = dotPos.get(index)[1];
        // 尝试在这里填入每一个数
        for (int k = 1; k <= 9; k++) {
            if (partSet[getEdge(i, j)][k] || rowSet[i][k] || columnSet[j][k])
                continue;
            // k可以选
            board[i][j] = (char) (k + '0');
            partSet[getEdge(i, j)][k] = true;
            rowSet[i][k] = true;
            columnSet[j][k] = true;
            solveSudokuBackTrace(index + 1, dotPos, board, partSet, rowSet, columnSet);
            if (isFind) return;
            partSet[getEdge(i, j)][k] = false;
            rowSet[i][k] = false;
            columnSet[j][k] = false;
            board[i][j] = '.';
        }
    }

    private int getEdge(int x, int y) {
        return (x / 3) * 3 + y / 3;
    }

    public static void main(String[] args) {
        MyBackTrace5 m = new MyBackTrace5();
        char[][] board = {
                {'5','3','4','6','7','8','9','.','2'},
                {'6','7','2','1','9','5','3','4','8'},
                {'.','9','8','3','4','2','5','6','7'},
                {'8','5','9','7','6','.','4','2','3'},
                {'4','2','6','8','5','3','7','9','1'},
                {'7','.','3','9','2','4','8','5','6'},
                {'9','6','.','5','3','7','2','8','4'},
                {'2','8','7','4','1','9','6','3','5'},
                {'.','.','.','.','8','.','.','7','9'}
        };
        for (char[] row : board) {
            for (char c : row) {
                System.out.print(c + " ");
            }
            System.out.println();
        }
        m.solveSudoku(board);
        for (char[] row : board) {
            for (char c : row) {
                System.out.print(c + " ");
            }
            System.out.println();
        }
    }
}
